package myself.a003MergeSort;

import myself.a000util.Constants;
import myself.a000util.Logarithm;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/22
 * Time 13:56
 * Mail 739153436@qq.com
 */
public class MergeSort {

    public static void main(String[] args) {
        Logarithm.MergeSort.check(MergeSort.class, Constants.normalSort);
    }

    public void sort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        sort(arr, left, mid);
        sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int tempIndex = 0;
        int lp = left;
        int rp = mid + 1;

        while (lp <= mid && rp <= right) {
            temp[tempIndex++] = arr[lp] <= arr[rp] ? arr[lp++] : arr[rp++];
        }

        while (lp <= mid) {
            temp[tempIndex++] = arr[lp++];
        }

        while (rp <= right) {
            temp[tempIndex++] = arr[rp++];
        }

        for (int i = 0; i < temp.length; i++) {
            arr[left + i] = temp[i];
        }
    }
}
